//
// Created by deng on 18-11-28.
//

#ifndef DOUDIZHU_ENDGAME_NEGAMAX_H
#define DOUDIZHU_ENDGAME_NEGAMAX_H

#include <unordered_map>
#include <vector>

#include "cardset.h"
#include "ddz_hand.h"
#include <deque>

using namespace std;
namespace doudizhu_endgame {

#define TRANSPOSITION_TABLE_INIT_SIZE 3000000

    struct TreeNode {
        int8_t turn;       //角色轮次 0: lord 1:farmer
        int8_t score; //-1表示对手赢
        CardSet lord;//出牌后的双方手牌
        CardSet farmer;
        Pattern *last_move;//上一次出的牌
        std::vector<TreeNode *> child;//可以做出的出牌选择
    };

    class TranspositionTable {
    public:

        TranspositionTable() {
            table_.reserve(TRANSPOSITION_TABLE_INIT_SIZE);
        }

        ~TranspositionTable() = default;

        size_t size();

        void add(TreeNode *node);

        //return score from table, if not in table return 0
        int8_t get(TreeNode *node);

    private:
        //value=score
        //置换表: key为TreeNode的hash值，value是分值
        std::unordered_map<uint64_t, int8_t> table_;

        uint64_t gen_key(TreeNode *node);
    };

    class Negamax {
    public:

        Negamax();

        ~Negamax();

        TreeNode *search(const CardSet &lord, const CardSet &farmer);

        //for research
        TreeNode *search(const CardSet &lord, const CardSet &farmer, Pattern *last);

        size_t nodes_searched() {
            return nodes_searched_;
        }

        double hash_hit_rate() {
            return ((double) hash_hit_ / nodes_searched_) * 100;
        }

    private:

        TreeNode *tree_;
        TranspositionTable table_;
        DouDiZhuHand doudizhu_;

        size_t nodes_searched_{};
        size_t hash_hit_{};

        int8_t negamax(TreeNode *node);

        void dumpSearch(TreeNode *node, deque<TreeNode *> &q);

        void gen_nodes(TreeNode *node);

        void pruning_tree(TreeNode *node);

        void destroy_tree(TreeNode *node);

    };

} //namespace doudizhu_endgame

#endif //DOUDIZHU_ENDGAME_NEGAMAX_H
